package javaInterview;

import java.util.*;

/**
 * 凯撒密码 - 模式匹配问题
 * 
 * 题目描述：
 * 小Q在路上捡到了一张字条，上面写了一个数组a。小Q猜测这些数字可能是某种机械密码，
 * 于是他找来了一堆字符串，请你判断它对这个字符串里哪些字符串是匹配字条上的数字模板的？
 * 
 * 当字符串s同时满足以下所有条件时才视为匹配模板：
 * 1. 字符串s的长度等于数组a的元素数量
 * 2. 数组a中相同的数字对应字符串s中相同的字符。即，若a[i]=a[j]，则s[i]=s[j]
 * 3. 字符串s中相同的字符对应数组a中相同的数字。即，若s[i]=s[j]，则a[i]=a[j]
 * 
 * 换句话说，字符串的字符与数组元素之间必须存在一一对应关系。
 * 
 * 例如：若a=[3,5,2,1,3]，则字符串"abfda"匹配模板，而"afbfa"不匹配，
 * 因为字母'f'对应数字1和5。
 * 
 * 时间限制：C/C++语言 1000MS；其他语言 3000MS
 * 内存限制：C/C++语言 65536KB；其他语言 589824KB
 */
public class CaesarPassword {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // 测试用例数量
        
        for (int test = 0; test < t; test++) {
            int n = scanner.nextInt(); // 数组a的长度
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            
            int m = scanner.nextInt(); // 字符串数量
            scanner.nextLine(); // 消费换行符
            
            for (int i = 0; i < m; i++) {
                String s = scanner.nextLine().trim();
                if (isMatch(a, s)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
        
        scanner.close();
    }
    
    /**
     * 判断字符串s是否与数组a匹配
     * 
     * 思路：
     * 1. 首先检查长度是否相等
     * 2. 使用两个HashMap维护双向映射关系：
     *    - numToChar: 数字 -> 字符的映射
     *    - charToNum: 字符 -> 数字的映射
     * 3. 遍历数组和字符串，检查映射关系是否一致
     * 
     * 时间复杂度：O(n)，其中n是数组/字符串的长度
     * 空间复杂度：O(n)
     */
    public static boolean isMatch(int[] a, String s) {
        int n = a.length;
        
        // 1. 长度必须相等
        if (s.length() != n) {
            return false;
        }
        
        // 2. 使用两个HashMap维护双向映射
        Map<Integer, Character> numToChar = new HashMap<>();
        Map<Character, Integer> charToNum = new HashMap<>();
        
        // 3. 遍历检查映射关系
        for (int i = 0; i < n; i++) {
            int num = a[i];
            char ch = s.charAt(i);
            
            // 检查数字到字符的映射
            if (numToChar.containsKey(num)) {
                // 如果该数字已经映射过，检查是否映射到相同的字符
                if (numToChar.get(num) != ch) {
                    return false;
                }
            } else {
                // 如果该数字还未映射，建立映射
                numToChar.put(num, ch);
            }
            
            // 检查字符到数字的映射
            if (charToNum.containsKey(ch)) {
                // 如果该字符已经映射过，检查是否映射到相同的数字
                if (charToNum.get(ch) != num) {
                    return false;
                }
            } else {
                // 如果该字符还未映射，建立映射
                charToNum.put(ch, num);
            }
        }
        
        return true;
    }
    
    /**
     * 测试用例
     * 
     * 解释样例1：数组 [3, 5, 2, 1, 3]
     * - "abfda": a→3, b→5, f→2, d→1, a→3
     *   建立映射：3↔a, 5↔b, 2↔f, 1↔d
     *   所有映射关系一致，匹配成功 ✓
     * 
     * - "afbfa": a→3, f→5, b→2, f→1, a→3
     *   问题：字符'f'在位置1对应数字5，在位置3对应数字1
     *   违反了"相同字符必须对应相同数字"的规则，匹配失败 ✗
     * 
     * 解释样例2：数组 [5, -3, 5, -3]
     * - "aaaa": a→5, a→-3, ...
     *   问题：字符'a'同时对应5和-3，匹配失败 ✗
     * 
     * - "bcbc": b→5, c→-3, b→5, c→-3
     *   建立映射：5↔b, -3↔c
     *   所有映射关系一致，匹配成功 ✓
     */
    public static void test() {
        System.out.println("==================== 凯撒密码测试 ====================\n");
        
        System.out.println("【测试样例1】数组: [3, 5, 2, 1, 3]");
        int[] a1 = {3, 5, 2, 1, 3};
        testString(a1, "abfda", true, "建立映射 3↔a, 5↔b, 2↔f, 1↔d");
        testString(a1, "afbfa", false, "字符'f'对应了两个不同的数字(5和1)");
        
        System.out.println("\n【测试样例2】数组: [5, -3, 5, -3]");
        int[] a2 = {5, -3, 5, -3};
        testString(a2, "aaaa", false, "字符'a'对应了两个不同的数字(5和-3)");
        testString(a2, "bcbc", true, "建立映射 5↔b, -3↔c");
        testString(a2, "aba", false, "长度不匹配(字符串长度3，数组长度4)");
        testString(a2, "cbcb", true, "建立映射 5↔c, -3↔b");
        
        System.out.println("\n【测试样例3】数组: [-3, -3]");
        int[] a3 = {-3, -3};
        testString(a3, "ab", false, "两个相同的数字-3对应了不同的字符(a和b)");
        testString(a3, "abc", false, "长度不匹配(字符串长度3，数组长度2)");
        testString(a3, "aa", true, "建立映射 -3↔a");
        
        System.out.println("\n【测试样例4】数组: [1]");
        int[] a4 = {1};
        testString(a4, "a", true, "建立映射 1↔a");
        testString(a4, "b", true, "建立映射 1↔b");
        
        System.out.println("\n=====================================================");
    }
    
    /**
     * 辅助测试方法
     */
    private static void testString(int[] a, String s, boolean expected, String reason) {
        boolean result = isMatch(a, s);
        String status = result == expected ? "✓" : "✗";
        System.out.printf("  \"%s\" → %s %s (期望: %s) - %s\n", 
            s, 
            result ? "YES" : "NO", 
            status, 
            expected ? "YES" : "NO",
            reason);
    }
}

